8.8 KB · ⇊ 6 parts · ⤓ Micron 8.8 KB · ⤓ HTML 67.4 KB

top

In computability theory, a set of natural numbers is computable (or decidable or recursive) if there is an algorithm that computes the membership of every natural number in a finite number of steps. A set is noncomputable (or undecidable) if it is not computable.

• Definition

• Examples

• Non-examples

• Properties

• See also

• Notes

• References

• Bibliography

• External links

A subset S {\displaystyle S} of the natural numbers is computable if there exists a total computable function f {\displaystyle f} such that:

f ( x ) = 1 {\displaystyle f(x)=1} if x ∈ ∈ S {\displaystyle x\in S}

f ( x ) = 0 {\displaystyle f(x)=0} if x ∉ ∉ S {\displaystyle x\notin S} .

In other words, the set S {\displaystyle S} is computable if and only if the indicator function 1 S {\displaystyle \mathbb {1} _{S}} is computable.

• Every recursive language is computable.

• Every finite or cofinite subset of the natural numbers is computable.

• The empty set is computable.

• The entire set of natural numbers is computable.

• Every natural number is computable.cite-ref-set-natural-number-1-0[note 1]

• The subset of prime numbers is computable.

• The set of Gödel numbers is computable.cite-ref-g-del-numbers-2-0[note 2]

• The set of Turing machines that halt is not computable.

• The set of pairs of homeomorphic finite simplicial complexes is not computable.cite-ref-3[1]

• The set of busy beaver champions is not computable.

• Hilbert's tenth problem is not computable.

Both A, B are sets in this section.

• If A is computable then the complement of A is computable.

• If A and B are computable then:

• A ∩ B is computable.

• A ∪ B is computable.

• The image of A × B under the Cantor pairing function is computable.

In general, the image of a computable set under a computable function is computably enumerable, but possibly not computable.

• A is computable if and only if A and the complement of A are both computably enumerable(c.e.).

• The preimage of a computable set under a total computable function is computable.

• The image of a computable set under a total computable bijection is computable.

A is computable if and only if it is at level Δ Δ 1 0 {\displaystyle \Delta _{1}^{0}} of the arithmetical hierarchy.

A is computable if and only if it is either the image (or range) of a nondecreasing total computable function, or the empty set.

• Computably enumerable

• Decidability (logic)

• Recursively enumerable language

• Recursive language

• Recursion

cite-note-set-natural-number-1note 1. ↑ That is, under the Set-theoretic definition of natural numbers, the set of natural numbers less than a given natural number is computable.

cite-note-g-del-numbers-2note 2. ↑ c.f. Gödel's incompleteness theorems; "On formally undecidable propositions of Principia Mathematica and related systems I" by Kurt Gödel.

cite-note-31. ↑ citerefmarkov1958Markov, A. (1958). "The insolubility of the problem of homeomorphy". Doklady Akademii Nauk SSSR. 121: 218–220. MR 0097793.

• Cutland, N. Computability. Cambridge University Press, Cambridge-New York, 1980. ISBN 0-521-22384-9; ISBN 0-521-29465-7

• Rogers, H. The Theory of Recursive Functions and Effective Computability, MIT Press. ISBN 0-262-68052-1; ISBN 0-07-053522-1

• Soare, R. Recursively enumerable sets and degrees. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1987. ISBN 3-540-15299-7

• reference-mathworld-recursive-setciterefweissteinSakharov, Alex. "Recursive Set". MathWorld.